The complexity of approximately counting in 2-spin systems on $k$-uniform bounded-degree hypergraphs

摘要

One of the most important recent developments in the complexity ofapproximate counting is the classification of the complexity of approximatingthe partition functions of antiferromagnetic 2-spin systems on bounded-degreegraphs. This classification is based on a beautiful connection to the so-calleduniqueness phase transition from statistical physics on the infinite$\Delta$-regular tree. Our objective is to study the impact of thisclassification on unweighted 2-spin models on $k$-uniform hypergraphs. As hasalready been indicated by Yin and Zhao, the connection between the uniquenessphase transition and the complexity of approximate counting breaks down in thehypergraph setting. Nevertheless, we show that for every non-trivial symmetric$k$-ary Boolean function $f$ there exists a degree bound $\Delta_0$ so that forall $\Delta \geq \Delta_0$ the following problem is NP-hard: given a$k$-uniform hypergraph with maximum degree at most $\Delta$, approximate thepartition function of the hypergraph 2-spin model associated with $f$. It isNP-hard to approximate this partition function even within an exponentialfactor. By contrast, if $f$ is a trivial symmetric Boolean function (e.g., anyfunction $f$ that is excluded from our result), then the partition function ofthe corresponding hypergraph 2-spin model can be computed exactly in polynomialtime.